#include <stdexcept>
#ifdef __COLLECTIONH__
#define WARNING__REDEFINE
#endif
#ifndef __COLLECTIONH__
#define __COLLECTIONH__

//#define DEBUG

#define BEGIN_SIZE 1 // Control the size of extra-space
#define   END_SIZE 1   // e.g. tag for something
#define COUNT_TO_INDEX(count) count - 1
#define INDEX_TO_COUNT(index) index + 1

#define begin_start_pos  0
#define begin_finish_pos 0 + BEGIN_SIZE

#define end_start_pos  BEGIN_SIZE + current_items
#define end_finish_pos BEGIN_SIZE + current_items + END_SIZE

template <typename Type> struct Pair
{
    int key;
    Type value;
};
static int test = 10;

template <typename T> class Collection
{
  public:
    Collection(int _delta = 3)
        : delta(_delta), T_ptr_list(new T *[BEGIN_SIZE + delta + END_SIZE]), empty(true), current_items(0),
          cache_size(0)
    {
        for (int i = begin_start_pos; i < begin_finish_pos; i++)                                //Init for Begin()
        {
            T_ptr_list[i] = new T;
            *T_ptr_list[i] = test;
            test+=10;
        }
        for (int i = end_start_pos; i < end_finish_pos; i++) // Init for End()
        {
            T_ptr_list[i] = new T;
            *T_ptr_list[i] = test;
            test+=10;
        }
        cache_size += BEGIN_SIZE + delta + END_SIZE;
    }

    Collection(const Collection<T> &other) // TODO: Realize Deep copy
        : delta(other.delta), cache_size(other.cache_size), T_ptr_list(new T *[BEGIN_SIZE + cache_size + delta + END_SIZE]), empty(other.empty),
          current_items(other.current_items)
    {
        //T_ptr_list = new T *[BEGIN_SIZE + cache_size + delta + END_SIZE];
        for (int i = 0; i < end_finish_pos; i++)
        {
            T_ptr_list[i] = new T(5);
            if (T_ptr_list[i])
                *T_ptr_list[i] = *(other.T_ptr_list[i]);
            //  TODO:  Or Replace them with:
            // T_ptr_list[i] = new T(*(other.T_ptr_list[i]));
        }
    }

    T &operator=(const Collection<T> &other) // TODO: Realize Deep copy
    {
        delta = other.delta;
        empty = other.empty;
        current_items = other.current_items;
        cache_size = other.cache_size;
        T_ptr_list = new T *[BEGIN_SIZE + cache_size + delta + END_SIZE];
        for (int i = 0; i < end_finish_pos; i++)
        {
            T_ptr_list[i] = new T;
            if (T_ptr_list[i])
                *T_ptr_list[i] = *(other.T_ptr_list[i]);
            //  TODO:  Or Replace them with:
            // T_ptr_list[i] = new T(*(other.T_ptr_list[i]));
        }
        return other;
    }

    ~Collection()
    {
        if (T_ptr_list != nullptr)
            for (int i = 0; i < end_finish_pos && !empty; ++i)
            {
                if (T_ptr_list[i] != nullptr)
                {
#ifdef DEBUG
                    if (i >= BEGIN_SIZE && i < current_items + END_SIZE)
                        std::cout << "Deleting element " << *T_ptr_list[i] << " at " << T_ptr_list[i] << "\n";
#endif
                    //T_ptr_list[i] = nullptr;
                    delete T_ptr_list[i];
                }
#ifdef DEBUG
                else
                {
                    std::cerr << "Warning: Attempting to delete a null pointer at index " << i << std::endl;
                }
#endif
            }
#ifdef DEBUG
        else
            std::cerr << "Warning: Attempting to delete a null pointer array" << std::endl;
        // 释放指针数组本身
#endif
        delete[] T_ptr_list;
    }

    void add(T item)
    {
        if (!T_ptr_list )
        {
            return;
        }
        if (INDEX_TO_COUNT(end_finish_pos) + 1 >= cache_size)
        {
            resize(delta);
        }
        T_ptr_list[end_finish_pos] = new T;
        //*T_ptr_list[end_finish_pos] = test; test+=10;
        for (int i = end_finish_pos; i >= end_start_pos; i--)
        {
            //printf("%d is covering by %d\n", *this->visit(i), *this->visit(i-1));
            this->visit(i) = this->visit(i - 1);
        }
        //delete T_ptr_list[end_start_pos];
        T_ptr_list[end_start_pos] = new T;
        *T_ptr_list[end_start_pos] = item;
        //T_ptr_list[end_finish_pos] = new T;
#ifdef DEBUG              
        std::cout << "Element Created " << *T_ptr_list[end_start_pos] << " at " << T_ptr_list[end_start_pos] << "\n";
#endif
        if(!empty)
            empty = false;
        current_items++;
        return;
    }
    void absorb(T *item_ptr)
    {
        if (!T_ptr_list)
        {
            return;
        }
        if (INDEX_TO_COUNT(end_finish_pos) + 1 >= cache_size)
        {
            resize(delta);
        }
        T_ptr_list[end_finish_pos] = new T;
        //*T_ptr_list[end_finish_pos] = test;
        //test += 10;
        for (int i = end_finish_pos; i >= end_start_pos; i--)
        {
            this->visit(i) = this->visit(i - 1);
        }
        T_ptr_list[end_start_pos] = item_ptr;
        if (!empty)
            empty = false;
        current_items++;
        return;
    }

    int melt()
    {
        if (current_items < 1)
        {
            return -1;
            empty = true;
        }
        for (int i = end_start_pos; i <= end_finish_pos-1; i++)
        {
            printf("%d is covering by %d\n", *this->visit(i - 1), *this->visit(i));
            this->visit(i - 1) = this->visit(i);
        }
#ifdef DEBUG
        if (!T_ptr_list[end_start_pos])
        {
            std::cerr << "Warning: Attempting to delete a null pointer at index " << current_items << std::endl;
            return -1;
        }
        std::cout << "Deleting element " << *this->visit(end_finish_pos-1) << " at " << this->visit(end_finish_pos-1)
                  << "\n";
#endif
        current_items--;
        if (end_finish_pos - 1 <= cache_size - delta)
            resize(-delta);
        return 1;
    }

    int melt(T *item)
    {
        if (current_items - 1 < 0)
        {
            return -1;
            empty = true;
        }
        if (current_items - 1 <= cache_size-delta)
            resize(-delta);
        for (auto &element : T_ptr_list)
            if (element == item)
            {
                delete element;
                //element = nullptr;
                current_items--;
            }
    }
    int& size()
    {
        return current_items;
    }
    int& length()
    {
        return current_items;
    }

    // use the VIRTUAL index to visit element
    T &at(int i, bool range_check = true,
          bool valid_check = true) // NOTICE: provide out_of_range check and valid element check (safely visit elements)
    {
        if ((i < 0 || i >= current_items )&& range_check)
        { 
            throw std::out_of_range("Index out of range");
        }
        if (T_ptr_list[i + BEGIN_SIZE] == nullptr && valid_check)
        {
            throw std::logic_error("Element didn't exist");
        }
        return *T_ptr_list[ BEGIN_SIZE + i ];
    }

    //use the ACTUAL index to visit pointer
    // NOTICE: this method are used to visit space more causally(not that safe but more free)
    T*& visit(int i, bool valid_check = true)
    {
#ifdef DEBUG
        //std::cout << "Visiting instance at Actual index " << i <<"\n";
#endif
        if (i < 0 || i >= cache_size )
        {
            throw std::length_error("Illegal address visited");
        }
        if (T_ptr_list[i] == nullptr && valid_check)
        {
            throw std::invalid_argument(
                "element is nullptr(invalid visit)\npls use [] or make \"valid_check=false\" to visit it");
        }
        return T_ptr_list[i];
    }

    

    T& operator[](int i) // directly visit certain element
    {

        return *T_ptr_list[ BEGIN_SIZE + i ];
    }

    T& begin() // the first element
    {
        return *T_ptr_list[ begin_finish_pos ];
    }
    T& end() // the last element
    {
        return *T_ptr_list[ end_start_pos - 1 ];
    }

    /*
    void remove(T item)
    {
        return;
	}
    void remove(int index)
    {
        return;
	}
	*/

    
  private:
    int delta;
    T **T_ptr_list;
    bool empty;
    int current_items;
    int cache_size;
// TODO:   |0|begin|...|current_items+1(end)|preserved|...|t_max_num|;
    int resize(int delta)
    {
        if (cache_size + delta < BEGIN_SIZE + END_SIZE)
            return -1;
        T **templist = T_ptr_list;
        T_ptr_list = new T *[BEGIN_SIZE + cache_size + delta + END_SIZE];
        for (int i = 0; i < end_finish_pos; i++)
        {
			T_ptr_list[i] = templist[i];
        }
        delete[] templist;
        cache_size += delta;
		return 0;
    }


    int rebuild(int delta)
    {
        if (cache_size + delta < BEGIN_SIZE + END_SIZE)
            return -1;
        T **temp_list = new T *[end_finish_pos];
        for (int i = 0; i < end_finish_pos; ++i)
        {
            temp_list[i] = T_ptr_list[i];
        }
        delete[] T_ptr_list;
        T_ptr_list = new T *[BEGIN_SIZE + cache_size + delta + END_SIZE];

        for (int i = 0; i < end_finish_pos; ++i)
        {
            if (i >= BEGIN_SIZE && i < BEGIN_SIZE + current_items)
            {
                T_ptr_list[i] = new T(*temp_list[i]); //deep copy
            }
            else
            {
                T_ptr_list[i] = nullptr; //
            }
        }
        for (int i = 0; i < end_finish_pos; ++i)
        {
            if (temp_list[i] != nullptr)
            {
                delete temp_list[i];
            }
        }
        delete[] temp_list;
        cache_size += delta;
        return 0;
    }
};
#endif